package chuan;

/**
 * create by Sun
 * 2018/9/2
    获取最长的公共子序列，连续的

 */
public class zuichanglianxugonggongzixulie {
    static String huoqu(String s1,String s2){
        if(s1.length()==0|| s2.length()==0){
            System.out.println(0);
            return null;
        }
        int[][] dp=new int[s1.length()][s2.length()];
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)==s2.charAt(0)){
                dp[i][0]=1;
            }else
                dp[i][0]=0;
        }
        for(int i=0;i<s2.length();i++){
            if(s2.charAt(i)==s1.charAt(0)){
                dp[0][i]=1;
            }else{
                dp[0][i]=0;
            }
        }
        for(int i=1;i<s1.length();i++){
            for(int j=1;j<s2.length();j++){
                if(s1.charAt(i)==s2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=0;
                }
            }
        }
        int max=0;
        int end=0;
        for(int i=0;i<s1.length();i++){
            for (int j=0;j<s2.length();j++){
                if(dp[i][j]>max){
                    max=dp[i][j];
                    end=i;
                }
            }
        }
        System.out.println();
        return s1.substring(end-max+1,end+1);
    }
    public static void main(String[] args) {
        String str1 ="GCCCTAGCCAGDE";
        String str2 = "GCGCCAGTGDE";

        String s = huoqu(str1, str2);
        System.out.println(s);
    }
}
